package com.wngbms.geektime.wangzheng;

public class _028 {

    public static void main(String[] args) {

    }

    public static class Heap {

        private int[] a;
        /**
         * 可以保存的总数
         */
        private int n;
        /**
         * 已保存元素个数
         */
        private int count;

        public Heap(int capacity) {
            a = new int[capacity + 1];
            n = capacity;
            count = 0;
        }

        /**
         * 大根堆, 排序后 元素 从小到大
         *
         * @param a   原始数组(未排序)
         * @param n   元素个数
         */
        public static void sort(int[] a, int n) {
            // 建堆, 堆顶元素最大, 每个节点都大于其左右子节点
            buildHeap(a, n);
            int k = n;
            while (k > 1) {
                // 交换堆顶, 和最后一个元素
                swap(a, 1, k);
                k--;
                //
                heapify(a, k, 1);
            }
        }

        /**
         * 建堆, 完成后 每个节点 都大于其 左右子节点
         *
         * @param a
         * @param n  数组元素个数
         */
        public static void buildHeap(int[] a, int n) {
            for (int i = n / 2; i >= 1; i--) {
                heapify(a, n, i);
            }
        }

        public void insert(int data) {
            if (count >= n) {
                throw new RuntimeException("out of index");
            }

            // 把新元素放到最后
            a[++count] = data;
            int index = count;
            int parentIndex;

            // 冒泡交换不满足条件的
            while ((parentIndex = index / 2) >= 1 && a[parentIndex] < a[index]) {
                swap(a, parentIndex ,index);
                index = index / 2;
            }
        }

        public int removeMax() {
            if (count < 1) {
                throw new RuntimeException("no element");
            }
            int result = a[1];
            heapify(a, count, 1);
            return result;
        }

        /**
         *
         * @param a     源数组
         * @param count 元素总数
         * @param index 待堆化下标
         */
        public static void heapify(int[] a, int count, int index) {
            while (true) {
                // 待堆化 左子索引
                int leftIdx = index * 2;
                // 待堆化 右子索引
                int rightIdx = leftIdx + 1;

                // 待交换元素索引, 不断递增
                int swapIndex = index;
                // 待堆化元素
                int curr = a[swapIndex];

                // 小于 左子
                if (leftIdx <= count && curr < a[leftIdx]) {
                    swapIndex = leftIdx;
                }
                // 小于 右子
                if (rightIdx <= count && curr < a[rightIdx]) {
                    swapIndex = rightIdx;
                }

                // 当前节点 大于 左右子节点
                if (swapIndex == index) {
                    break;
                }

                swap(a, index, swapIndex);
                index = swapIndex;
            }
        }

        public static void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

}
